/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

/**
 *
 * @author Administrator
 */
import java.util.*;

public class LC1416_VIP {

    static class Solution {

        /**
         * @param num: The arry you should handle
         * @return: Return the array
         */
        public int[] getPreviousNumber(int[] num) {
            //单调栈
            Stack<List<Integer>> stack = new Stack<>();
            int n = num.length;
            //[i][0]: i左边第一个比i小的位置
            //[i][1]: i右边第一个比i小的位置
            int[][] help = new int[n][2];

            for (int i = 0; i < n; i++) {

                while (!stack.isEmpty() && num[stack.peek().get(stack.peek().size() - 1)] > num[i]) {
                    List<Integer> idxs = stack.pop();
                    int leftless = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                    for (int idx : idxs) {
                        help[idx][0] = leftless;
                        help[idx][1] = i;
                    }
                }

                if (!stack.isEmpty() && num[stack.peek().get(0)] == num[i]) {
                    stack.peek().add(i);
                } else {
                    List<Integer> ll = new ArrayList<>();
                    ll.add(i);
                    stack.add(ll);
                }
            }

            while (stack.size() > 0) {
                List<Integer> idxs = stack.pop();
                int leftless = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (int idx : idxs) {
                    help[idx][0] = leftless;
                    help[idx][1] = -1;
                }
            }

            int[] ans = new int[n];
            for (int i = 0; i < n; i++) {
                if (help[i][0] == -1) {
                    ans[i] = num[i];
                } else {
                    ans[i] = num[help[i][0]];
                }
            }
            return ans;

        }
    }

    public static void main(String[] args) {
        int[] p1 = {2, 3, 6, 1, 5, 5};

        Solution obj = new Solution();
        int[] ret1 = obj.getPreviousNumber(p1);
        for (int i : ret1) {
            System.out.print(i + " ");  //[2,2,3,1,1,1]
        }

        System.out.println();

        int[] p2 = {6, 3, 1, 2, 5, 10, 9, 15};

        int[] ret2 = obj.getPreviousNumber(p2);
        for (int i : ret2) {
            System.out.print(i + " ");  //[2,2,3,1,1,1]
        }

        System.out.println();
    }
}

/*
LintCode-Logo
学习
刷题
题集
群组

内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
1416 · 前一个数
算法
中等
通过率
64%
题目
题解7
笔记
讨论9
排名
记录
描述
给一个数组，对于每一个元素，找出它之前第一个比它小的元素的值。如果没有，则输出它本身。

Lintcode超级VIP年卡 618预售 享买一年送一年

微信加【jiuzhang1104】备注【VIP】即可参加


输入的数组长度为n，n <= 100000。
元素的大小为x，x <= 1000000。
第一个是指距离最近
样例
样例 1：

输入： list = [2,3,6,1,5,5]
输出：[2,2,3,1,1,1]
解释：依据题意，找出每个数字前面第一个比它小的元素。
样例 2：

输入： list = [6,3,1,2,5,10,9,15]
输出：[6,3,1,1,2,5,5,9]
解释：依据题意，找出每个数字前面第一个比它小的元素。
标签
企业
推特
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
1607/2083
已开启智能提示
发起考试
30 分 00 秒
123456789
public class Solution {
    /**
     * @param num: The arry you should handle
     * @return: Return the array

public int[] getPreviousNumber(int[] num) {
        // Write your code here
        }
        }
        控制台
        历史提交
样例 1：

输入： list = [2,3,6,1,5,5]
输出：[2,2,3,1,1,1]
解释：依据题意，找出每个数字前面第一个比它小的元素。
样例 2：

输入： list = [6,3,1,2,5,10,9,15]
输出：[6,3,1,1,2,5,5,9]
解释：依据题意，找出每个数字前面第一个比它小的元素。
 */
// LC 1416 · 前一个数 vip  中等  单调栈
